#include <iostream>
#include <cstring>
using namespace std;

const int N=1e3+10;
const int MOD=1e9+7;

int f[N],g[N];

int main()
{
	int n,V;
	cin>>n>>V;
	memset(f,-0x3f,sizeof(f));
	f[0]=0;
	g[0]=1;
	for(int i=1;i<=n;i++)
	{
		int v,w;
		cin>>v>>w;
		for(int j=V;j>=v;j--)
		{
			int maxv=max(f[j],f[j-v]+w);
			int cnt=0;
			if(maxv == f[j])
				cnt+=g[j];
			if(maxv == f[j-v]+w)
				cnt+=g[j-v];
			g[i]=cnt%MOD;
			f[j]=maxv;
		}
	}
	int res=0;
	for(int i=0;i<=V;i++)
	{
		res=max(res,f[i]);
		cout<<f[i]<<' ';		
	}
cout<<endl;
	int cnt=0;
	for(int i=0;i<=V;i++)
	{
		cout<<g[i]<<' ';
		if(f[i]==res)
			cnt=(cnt+g[i])%MOD;
	}
	
	cout<<endl;
	cout<<cnt;
	return 0;
}
